package com.hatricks.is.algorithm.maxcommonstr;

public class LongestCommonSubstring {

    public static String longestCommonSubstring(String s1, String s2) {
        if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) {
            return "";
        }
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1]; // DP 表
        int maxLength = 0; // 最长公共子串的长度
        int endIndex = 0; // 最长公共子串在 s1 中的结束位置
        // 填充 DP 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i; // 更新结束位置
                    }
                } else {
                    dp[i][j] = 0; // 不匹配时重置为 0
                }
            }
        }
        // 提取最长公共子串
        if (maxLength == 0) {
            return ""; // 没有公共子串
        }
        return s1.substring(endIndex - maxLength, endIndex);
    }

    public static String longestCommonSubstring5(String s1, String s2) {
        if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) {
            return "";
        }
        int m = s1.length();
        int n = s2.length();
        // 最长公共子串
        int[][] dp = new int[m + 1][n + 1];
        int maxStrLength = 0;
        int endIndex = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxStrLength) {
                        maxStrLength = dp[i][j];
                        endIndex = i; // 更新结束位置
                    }
                }
            }
        }
        return s1.substring(endIndex - maxStrLength, endIndex);
    }

    /**
     * 暴力法
     */
    public static String longestCommonSubstring1(String s1, String s2) {
        if (s1 == null || s2 == null) return null;
        String maxStr = "";
        for (int i = 0; i < s1.length(); i++) {
            for (int j = i + 1; j <= s1.length(); j++) {
                String sub = s2.substring(i, j);
                if (s1.contains(sub) && sub.length() > maxStr.length()) {
                    maxStr = sub;
                }
            }
        }
        return maxStr;
    }


    public static void main(String[] args) {
        String s1 = "abcdef";
        String s2 = "zbcdee";
        String result = longestCommonSubstring5(s1, s2);
        System.out.println("最长公共子串: " + result); // 输出: bcd
    }
}